package 左哥算法.ch10暴力递归;

import org.junit.Test;

public class Ch06一些动规题2 {
    /**
     * 力扣32. 最长有效括号
     * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
     */
    @Test
    public void ch01(){
        String args="(()()(()";
        System.out.println(longestValidParentheses2(args));
        System.out.println(longestValidParentheses1(args));
    }
    /**
     * ch01:暴力解思路：
     *      1.以每个位置作为起点往后匹配有效括号，找出每个位置的最长有效括号
     */
    public int longestValidParentheses1(String s) {
        char[] chars = s.toCharArray();
        int max=0;
        for (int i = 0; i < chars.length; i++) {
            int count=0;
            int j = i;
            int curr=0;
            if (chars[i]==')')continue;
            while (j<chars.length&&count>=0){   //需要i位置右侧最后一个count==-1的位置
                if (chars[j]=='('){
                    count++;
                }else {
                    count--;
                }
                if (count==0){
                    curr=j-i+1;
                }
                j++;
            }
            max=Math.max(curr,max);
        }
        return max;
    }

    /**
     * ch01：动态规划思路
     *  在1中，我们先枚举所有的位置，然后从该位置向右查找它的最长有效长度。
     *  如果可以提供一个数组，每个位置对应的最右侧count=-1的位置数组。
     *  那么我们就可以直接计算出每个位置的最长有效长度。
     *  但直接生成这样的数组代价有一点大。
     *  我们再观察数据，发现，该位置最右侧count=-1的位置为：该位置右一位的最长有效长度+1，或该位置右一位的最长有效长度+1+（该位置右一位的最长有效长度+1）的最长有效长度
     *  即：dp[i]=(dp[i+1]+1)==")"?dp[i+1]+2+dp[dp[i+1]+2];
     */
    public int longestValidParentheses2(String s) {
        char[] chars = s.toCharArray();
        int[] dp=new int[chars.length];
        int max=0;
        for (int i = dp.length - 2; i >= 0; i--) {
            if (chars[i]=='(' &&dp[i+1]+i+1<chars.length&& chars[dp[i+1]+i+1]==')'){    //当前位置右侧应该为 ‘)’ 括号位置dp[i+1]+i+1，是否为 ‘)’
                dp[i]=dp[i+1]+2;    //如果是，则当前长度至少为 从当前位置到该位置+1
                if (dp[i]+i<dp.length){ //在判断该位置的右侧是否还存在应该为 ')'的位置，该位置为dp[i]+i
                    dp[i]+=dp[i+dp[i]]; //存在则再加上
                }
                max=Math.max(dp[i],max);
            }
        }
        return max;
    }

    /**
     * ch02：给你一串数字，其中1对应a,2对应b...26对应z
     * 请问这串数字可以转化为多少种合法的字符串
     * todo：转dp...
     */
    @Test
    public void ch02(){
        System.out.println(ch02Fun1(111143311));
        System.out.println(ch02Fun2("111143311"));
    }
    public int ch02Fun1(long str){
        return fun1(String.valueOf(str).toCharArray(), 0);
    }
    public int fun1(char[] chars,int i){
        if (i==chars.length||chars[i]=='0'){
            return 1;
        }
        int res = fun1(chars, i + 1);   //当前位置单独转化
        if (i+1<chars.length    //存在下一个
                &&(chars[i]-'0')*10+chars[i+1]-'0'<=26   //且与下一个的和小于26
        ){
            res+=fun1(chars,i+2);   //两个位置一起转
        }
        return res;
    }

    /**
     * ch02：dp解法
     */
    public int ch02Fun2(String str){
        int N = str.length();
        int[] dp=new int[N +1];
        char[] chars = str.toCharArray();
        dp[N]=1;
        for (int i = N-1; i >= 0; i--) {
            dp[i]=dp[i+1];
            if (i+1 < N && chars[i]!='0' &&(chars[i]-'0')*10+chars[i+1]-'0'<=26){
                dp[i]+=dp[i+2];
            }
        }
        return dp[0];
    }

    /**
     * 重点题***
     * 题目：告诉你节点个数n,n>0，请问这么多节点的二叉树有多少种
     */
    @Test
    public void ch03(){
        int n=4;
        System.out.println(ch03fun1(n));
        System.out.println(ch03Dp(n));
    }
    @Test
    public void ch03Compare(){
        for (int i = 1; i <= 50; i++) {
            int fun = ch03Dp(i);
            int ans = ch03fun1(i);
            if (ans!= fun){
                System.out.println(i+":预期"+ans+"\t实际"+fun);
            }
        }
    }

    /**
     * ch03：错误思路1：
     *  每个节点有三种情况，左树为空，右树为空，都不为空
     *  所以结果=fun(n-1)+fun(n-1)+fun(n-2);
     *  -----------
     *  错误点：
     *      这三种情况存在子情况。所以并不是单纯的三种情况相加
     */
    public int ch03Error1(int n){
        if (n<0) return 0;
        if (n==1||n==0)return 1;
        return ch03Error1(n - 1) + ch03Error1(n - 1) + ch03Error1(n - 2);
    }
    /**
     * ch03：错误思路2：
     *   由错误1知，我们要考虑子情况。
     *   所以我们可以枚举出左树和右树所有的情况。
     *   思路为：
     *      放一个在当前节点。
     *          放i个在左树，放n-i个在右树
     *          左树放i个节点，右树放n-i个总情况为fun(i)+fun(n-i)
     * -------------
     * 错误点：
     *     这是一个分步计数问题。
     *     放左树和右树构成一个完整的事件。
     *     所以总情况不应该是fun(i)+fun(n-i)
     *     而应该是fun(i)*fun(n-i)
     */
    public int ch03Error2(int n){
        if (n<0) return 0;
        if (n==1||n==0)return 1;
        n--;    //放在当前位置
        int res=0;
        for (int i = 0; i <= n; i++) {//放i个在左树，其余全部放右树的的情况
            int left= ch03Error2(i);
            int right= ch03Error2(n - i);
            res+=left+right;
        }
        return res;
    }

    public int ch03fun1(int n){
        if (n<0) return 0;
        if (n==1||n==0)return 1;
        n--;
        int res=0;
        for (int i = 0; i <= n; i++) {
            int left= ch03fun1(i);
            int right= ch03fun1(n - i);
            res+=left*right;
        }
        return res;
    }
    public int ch03Dp(int n){
        int[] dp=new int[n+1];
        dp[0]=1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                dp[i]+=dp[j] * dp[i - j-1];
            }
        }
        return dp[n];
    }
}
